package teaching;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: fzykd
 * Date: 2022-11-13
 * Time: 15:07
 */

//快速排序
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[800000];
        //产生随机数
        for (int i = 0; i < 800000; i++) {
            arr[i] = (int) (Math.random()*800000); //生成[0-800000)数
        }

        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1 = simpleDateFormat.format(data1);
        System.out.println("排序前的时间输出=" + date1);

        //运行冒泡排序
        quickSort(arr,0, arr.length-1);

        Date data2 = new Date();
        String date2 = simpleDateFormat.format(data2);
        System.out.println("排序后的时间输出=" + date2);

    }

    //基本思想 排序数组从中间分为两个部分 以分割线为基准 左边都比基准小 右边都比基准大
    public static void quickSort(int[] arr,int left,int right){
        int l = left;
        int r = right;
        //基准 中间值
        int pivot = arr[(left+right)/2];

        int tmp = 0;
        //只要
        while (l < r){
            //在基准左边一直找 找到一个大于等于pivot,才退出
            while (arr[l] < pivot){
                l += 1;
            }
            //在pivot的右边一直找1 找到一个小于等于pivot值 才退出
            while (arr[r] > pivot){
                r -=1;
            }
            //如果 l >= r 那么pivot左边都是小于的 右边都是大于的
            if (l >= r){
                break;
            }
            //交换
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

            //如果交换完之后 发现这个arr[l] == pivot 相等  那么-- 前移
            if (arr[l] == pivot ){
                r -= 1;
            }
            //如果交换完之后 发现这个arr[r] == pivot 相等  那么++ 后移
            if (arr[r] == pivot){
                l +=1;
            }
        }

        //如果1 == r必须l++ , r-- 否则会出现栈溢出
        if (l == r){
            l +=1;
            r -=1;
        }
        //向左递归
        if (left < r){
            quickSort(arr,left,r);
        }
        //向右递归
        if (right > l){
            quickSort(arr,l,right);
        }

    }
}
